All Questions
Tagged with integer-programmingds.algorithms
21 questions
0votes
0answers
106views
$\mathsf{GCD}(a,b)\not\in TC^0$ while fixed dimension feasibility $ILP$ is in $TC^0$ consistent with our knowledge?
The reduction from $\mathsf{GCD}(a,b)$ is to do binary search on the feasibility of program $$r_1<au+bv<r_2$$ $$u,v\in\mathbb Z$$ where $a,b$ are given integers and we do binary search with ...
- 13.5k
2votes
1answer
140views
Do there exist two equivalent objective functions one of which can be approximated but another one cannot?
I have two equivalent problems A and B, meaning that the optimal solution of one must be the optimal solution of another one. However, it seems that problem A can be approximated but B cannot. Below ...
user53330
3votes
1answer
377views
How hard is this combinatorial optimisation problem?
Suppose we have multiple intervals $R_1,R_2,...,R_i$ of non-negative integers. These intervals may overlap and we use $R_h(\mathrm{median})$ to denote the median integer in the $h$-th interval $R_h$, ...
user53330
2votes
1answer
296views
Characterization of integral polyhedra
A rational polyhedron $P \subseteq \mathbb{R}^n$ is an integral polyhedron if it is the convex hull of its integer points. That is, if $P = conv(P \cap \mathbb{Z}^n)$. Equivalently, $P$ is integral if ...
- 649
1vote
0answers
17views
Size of solutions in integer programming
Given a linear integer program $Ax\leq b$ with $A\in\mathbb Z^{m\times n}$ and $b\in\mathbb Z^m$ known is there a polynomial time algorithm to give tight upper bounds for $\log_2\|x\|_\infty$ and $\...
- 13.5k
6votes
1answer
208views
Anti bin packing
I have a (practically) unlimited amount of McDonald's coupons that I can use only if I shop for at least 1 money. Thus I want to partition my family's meal into as many parts as possible that all ...
- 14.4k
3votes
1answer
126views
Has Khachiyan/Porkolob's convex integer optimization been implemented?
Khachiyan and Porkolab in 'Integer optimization on convex semialgebraic sets' gave an $O(ld^{ O(k^4)})$ algorithm to minimize a degree $d$ form with integer coefficients of binary length at most $l$ ...
- 13.5k
5votes
1answer
212views
Have fixed parameter integer program algorithms ever been implemented for research use?
Have any fixed parameter integer programming algorithms described in Integer programming with a fixed number of variables been implemented? Is there a reference code that researchers can use?
- 13.5k
8votes
0answers
382views
What exactly did Lenstra prove on mixed integer linear program?
I studied Lenstra's paper https://www.jstor.org/stable/3689168. I have no clue what complexity he provides on Mixed Integer Programming (it is too terse and it is not a stand alone paper as he assumes ...
- 13.5k
7votes
1answer
142views
Quanitifier Free Presburger Arithmetic: Upper bound on solution size?
DISCLAIMER: I had originally posted this to CS.SE, but I've deleted it and moved it here, since it received little attention, and I think it is a research level question. According to this paper, if ...
- 3,014
4votes
2answers
305views
Lattice-based algorithms in practice
Are there any applications of lattice-based algorithms other than those in cryptography and integer programming? Could someone state a few papers where the primary algorithms use lattice-based LLL ...
- 121
2votes
0answers
81views
General covering approximation
Consider the following integer program (general covering): $\min c \cdot x$ subject to $Ax \ge b$, where all entries in $A, b, c$ are nonnegative and $x$ is required to be nonnegative and integral. ...
- 233
2votes
1answer
155views
Can Lenstra's algorithm output all feasible solutions in O^*(f(k)) time where k is the number of variables and f is a computable function in k?
It is well-known that Lenstra's famous algorithm (presented in the paper Integer programming with a fixed number of variables) can solve an ILP problem in $O^*(f(k))$ time where k is the number of ...
4votes
0answers
1kviews
How to determine proper rounding in linear programming relaxations?
Recall that in the vertex cover problem we are given an undirected graph ${G=(V,E)}$ and we want to find a minimum-size set of vertices ${S}$ that “touches” all the edges of the graph, that is, such ...
- 141
2votes
1answer
2kviews
Solve a simple system of linear inequalities in natural numbers
I want to find a solution to a system of linear inequalities of the following form \begin{aligned} a_1 + b &\ge a_2 \\\ \vdots \\\ a_4 + c &\ge a_1 \end{aligned} where $a_i \in \mathbb N \...
- 37
